﻿//void AdjustUp(HPDataType* a, int child) {
//	int parent = (child - 1) / 2;
//	while (child > 0)
//	{
//		if (a[child] > a[parent])
//		{
//			Swap(&a[child], &a[parent]);
//			child = parent;
//			parent = (parent - 1) / 2;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//void HPPush(HP* php, HPDataType x)
//{
//	assert(php);
//	if (php->size == php->capacity)
//	{
//		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
//		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
//		if (tmp == NULL)
//		{
//			perror("realloc fail");
//			return;
//		}
//		php->a = tmp;
//		php->capacity = newCapacity;
//	}
//	php->a[php->size] = x;
//	php->size++;
//	AdjustUp(php->a, php->size - 1);
//}

//void AdjustDown(HPDataType* a, int n, int parent)
//{
//	int child = parent * 2 + 1;
//	while (child < n)
//	{
//		// 假设法，选出左右孩⼦中⼩的那个孩⼦
//		if (child + 1 < n && a[child + 1] > a[child])
//		{
//			++child;
//		}
//		if (a[child] > a[parent])
//			Swap(&a[child], &a[parent]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//void HPPop(HP* php)
//{
//	assert(php);
//	assert(php->size > 0);
//	Swap(&php->a[0], &php->a[php->size - 1]);
//	php->size--;
//	AdjustDown(php->a, php->size, 0);
//}


// 1、需要堆的数据结构
// 2、空间复杂度 O(N)
//void HeapSort(int* a, int n)
//{
//	HP hp;
//	for (int i = 0; i < n; i++)
//	{
//		HPPush(&hp, a[i]);
//	}
//	int i = 0;
//	while (!HPEmpty(&hp))
//	{
//		a[i++] = HPTop(&hp);
//		HPPop(&hp);
//	}
//	HPDestroy(&hp);
//}


//// 升序，建⼤堆
//// 降序，建⼩堆
//// O(N*logN)
//void HeapSort(int* a, int n)
//{
//	// a数组直接建堆 O(N)
//	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
//	{
//		AdjustDown(a, n, i);
//	}
//	// O(N*logN)
//	int end = n - 1;
//	while (end > 0)
//	{
//		Swap(&a[0], &a[end]);
//		AdjustDown(a, end, 0);
//		--end;
//	}
//}

